// 解题思路：
// 题目要求求最长子序列，这是典型的动态规划的题目，但是题目要求时间复杂度为 nlogn，能达到 logn 的算法不多，一个堆，一个二分
// 这道题目是贪心 + 二分
// 首先要遍历数组，这个时间复杂度就到 n 了，剩下的需要用二分的策略
// 建立一个新的数组，数组下标表示子序列的长度，数组里存的内容是长度为 i 的子序列的最后一个元素的最小值
// 因此数组长度越长，保存的元素的值就越大，是单调递增的
// 再往后遍历数组找到的元素，判断能否拼接在哪个子序列后面的时候，就可以通过二分查找的方式来进行优化，不需要遍历
// 找到最大的元素值 且 小于 a[i] 的元素，下一个位置就是 a[i] 可以拼接到后面的位置
// 如果 a[i] < arr[pos], arr[pos] = a[i]
// 最后返回 arr 数组下标即可
// 如果 pos 为 0 或者 a[i] > arr[pos], 就在 ++pos 的位置新增这个元素

public class LongestIncrease {
    public int LIS (int[] a) {
        int n = a.length;
        int[] arr = new int[n + 1]; // arr[i] 表示长度为 i 的最小末尾
        int pos = 0;
        for(int i = 0; i < n; i++){
            if(pos == 0 || a[i] > arr[pos]){
                pos++;
                arr[pos] = a[i];
            }else{
                int left = 1; int right = pos; int mid = 0;
                while(left < right){
                    mid = (right - left) / 2 + left;
                    if(arr[mid] < a[i]){
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                if(arr[left] > a[i]) arr[left] = a[i];
            }
        }

        return pos;
    }
}
